/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2025-10-12
 * Time: 21:23
 */
public class TestH9 {
//    public static int jump(int[] num) {
//        int left = 0, right = 0, n = num.length;
//        int maxIndex = 0;
//        int ret = 0;
//        while(left <= right) {
//            for(int i = left; i <= right; i++) {
//                if(maxIndex >= n-1) {
//                    return ret;
//                }
//                if(num[i]+i > maxIndex) {
//                    maxIndex = num[i]+i;
//                }
//                left = right+1;
//                right = maxIndex;
//                ret++;
//            }
//        }
//        return -1;
//    }
    public static int jump(int[] nums) {
        int n = nums.length;
        // 到达i下标的最小步数
        int[] dp = new int[n];
        dp[0] = 0;
        for(int i = 1; i < n; i++) {
            dp[i] = Integer.MAX_VALUE;
            for(int j = i-1; j >= 0; j--) {
                if(nums[j]+j >= i) {
                    dp[i] = Math.min(dp[i],dp[j]+1);
                }
            }
        }
        return dp[n-1];

    }


    public static void main(String[] args) {
        int[] num = {2,3,1,1,4};
        int ret = jump(num);
        System.out.println(ret);

    }
}
